package com.Offer;

import com.pojo.ListNode;

/*
    面试题52：两个链表的第一个公共节点
    题目描述：输入两个链表，找出它们的第一个公共结点。
 */
public class demo52 {
    public static void main(String[] args) {
        ListNode pHead1 = new ListNode(3);
        pHead1.add(5);
        pHead1.add(10);
        pHead1.add(15);
        pHead1.add(17);
        pHead1.add(18);
        ListNode pHead2 = new ListNode(4);
        pHead2.add(6);
        pHead2.add(7);
        pHead2.add(10);
        pHead2.add(15);
        pHead2.add(17);
        pHead2.add(18);

        ListNode commonNode = FindFirstCommonNode(pHead1,pHead2);
        System.out.println(commonNode.val);

    }

    //使长的链表先走多余的步伐，然后再同时比较两个链表的节点值，最后得到第一个共同节点的值
    public static ListNode FindFirstCommonNode(ListNode pHead1,ListNode pHead2){
        int length1 = ListNode.getLength(pHead1);
        int length2 = ListNode.getLength(pHead2);
        int nLengthDif = length1-length2;
        ListNode longHead = pHead1;
        ListNode shortHead = pHead2;
        if(length2 > length1){
            longHead = pHead2;
            shortHead = pHead1;
            nLengthDif = length2-length1;
        }

        for(int i = 0;i < nLengthDif;i++){
            longHead = longHead.next;
        }
        while((longHead !=null) && (shortHead != null) && (shortHead.val != longHead.val) ){
            longHead = longHead.next;
            shortHead = shortHead.next;
        }

        ListNode res = longHead;
        return res;
    }

}
